public class LongestCommonSubsequence {

	public static void main(String[] args){
		String y = "BDCABA";
		String x = "ABCBDAB";
		lcsLength(x, y);
	}


	private static void lcsLength(String x, String y) {
		int m = x.length();
		int n = y.length();

		System.out.println("M = " + m);
		System.out.println("N = " + n);

		int b[][] = new int[m+1][n+1];
		int c[][] = new int[m+1][n+1];

		for(int i = 0; i < m ; ++i) {
			c[i][0] = 0;
		}

		for(int j = 0; j < n; ++j) {
			c[0][j] = 0;
		}


		for(int i = 1; i <= m; ++i ) {
			for(int j = 1; j <= n; ++j) {
				if(x.charAt(i-1) == y.charAt(j-1)) {
					c[i][j] = c[i-1][j-1] + 1;
					b[i][j] = 1;
				}else if (c[i-1][j] >= c[i][j-1]) {
					c[i][j] = c[i-1][j];
					b[i][j] = 0;
				} else {
					c[i][j] = c[i][j-1];
					b[i][j] = -1;
				}
			}
		}


		for(int i = 0; i <= m; ++i) {
			for(int j = 0; j <= n; ++j) {
				System.out.print(c[i][j] + " ");
			}
			System.out.println("");
		}

	}   

}

